package 回溯;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

/**
 * todo
 *
 * @author songZiHao
 * @version 1.0.0
 * @ClassName 二进制手表401.java
 * @createTime 2023年01月13日 11:08:00
 */
public class 二进制手表401 {
	Set<String> result = new HashSet<>();

	boolean[] hoursUsed = new boolean[4];
	boolean[] minutesUsed = new boolean[6];
	int[] minutes = new int[] {1, 2, 4, 8, 16, 32};
	int[] hours = new int[] {1, 2, 4, 8};

	public List<String> readBinaryWatch(int turnedOn) {
		backTrace(turnedOn, 0, hoursUsed, minutesUsed, 0, 0);
		return new ArrayList<>(result);
	}

	public void backTrace(int turnedOn, int curIndex, boolean[] hoursUsed, boolean[] minutesUsed, int hour, int minute) {
		//结束条件
		if (turnedOn == curIndex && hour <= 11 && minute <= 59) {
			StringBuilder sb = new StringBuilder();
			// 小时不会以零开头，比如 “01:00” 是不允许的，应为 “1:00”
			sb.append(hour).append(":");
			// 分钟必须由两位数组成，可能会以零开头，比如 “10:2” 是无效的，应为 “10:02”。
			if (minute < 10) {
				sb.append("0").append(minute);
			} else {
				sb.append(minute);
			}
			result.add(sb.toString());
			return;
		}
		for (int i = curIndex; i < turnedOn; i++) {
			//选择分钟
			for (int j = 0; j < minutesUsed.length; j++) {
				//分钟已经用掉了
				if (minutesUsed[j]) {
					continue;
				}
				//如果没用掉，校验分钟的合法性
				if (minute + minutes[j] > 59) {
					break;
				}
				//如果小于则进行下一个
				minutesUsed[j] = true;
				backTrace(turnedOn, i + 1, hoursUsed, minutesUsed, hour, minute + minutes[j]);
				minutesUsed[j] = false;
			}
			//选择小时
			for (int j = 0; j < hoursUsed.length; j++) {
				//小时已经用掉了
				if (hoursUsed[j]) {
					continue;
				}
				//如果没用掉，校验小时的合法性
				if (hour + hours[j] > 11) {
					break;
				}
				//如果小于则进行下一个
				hoursUsed[j] = true;
				backTrace(turnedOn, i + 1, hoursUsed, minutesUsed, hour + hours[j], minute);
				hoursUsed[j] = false;
			}
			//选择时间和分钟都不行则返回
			return;
		}
	}
}
